package org.korifey.ffalg;

import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;

import java.util.Arrays;
import java.util.Random;

import org.junit.Assert;
import org.junit.Test;

public class SortsTest {
	
	@Test
	public void testSorts() {
		int[][] arrs = new int[][] {
				{1},
				{1, 2},
				{1, 1},
				{2, 1},
				{1, 2, 3},
				{1, 2, 2},
				{1, 1, 2},
				{3, 2, 1},
				{3, 1, 2},
				{1, 2, 1, 3},
				{4, 3, 2, 1},
				{1, 2, 2, 3},
				{3, 2, 2, 1},
				{1, 2, 3, 4, 5},
				{5, 4, 4, 4, 4},
				{5, 1, 5, 1, 5},
				Probabilities.generateRandomArray(10, 0, 1),
				Probabilities.generateRandomArray(10, 0, 2),
				Probabilities.generateRandomArray(11, 0, 3),
		};
		for (int i=0; i<arrs.length; i++) {
			int[] et = arrs[i].clone();
			Arrays.sort(et);
			
			int[] inssorted = arrs[i].clone();
			Sorts.insertionSort(inssorted);
			Assert.assertArrayEquals(et, inssorted);
			
			int[] mergesorted = arrs[i].clone();
			Sorts.mergeSort(mergesorted);
			Assert.assertArrayEquals(et, mergesorted);
			
			int[] qsorted = arrs[i].clone();
			Sorts.quickSort(qsorted);
			Assert.assertArrayEquals(et, qsorted);

			int[] heapsorted = arrs[i].clone();
			Sorts.heapSort(heapsorted);
			Assert.assertArrayEquals(et, heapsorted);
		}
	}
	
	@Test
	public void testBsearch() {
		assertEquals(0, Sorts.bsearch(new int[] {1}, 1));
		assertEquals(0, Sorts.bsearch(new int[] {1,1}, 1));
		assertEquals(0, Sorts.bsearch(new int[] {1,1,1}, 1));
		assertEquals(0, Sorts.bsearch(new int[] {1,1,1,1}, 1));
		assertEquals(0, Sorts.bsearch(new int[] {1,2}, 1));
		assertEquals(0, Sorts.bsearch(new int[] {1,1,2}, 1));
		assertEquals(3, Sorts.bsearch(new int[] {1,2,3,4,5}, 4));
		assertEquals(3, Sorts.bsearch(new int[] {1,2,2, 3,3,3,4,5}, 3));
		
		Random r = new Random();
		for (int len=1; len < 10; len++) {
			int [] a = new int[len];
			for (int i=0; i<1000; i++) {
				for (int j=0; j<len; j++) a[j] = r.nextInt(10);
				int x = r.nextInt(10);
				int idx = Sorts.bsearch(a, x);
				if (idx >= 0) {
					assertEquals(a[idx], x);
				} else {
					if (idx != -a.length - 1) {
						assertTrue(a[-(idx+1)] > x);
					}
					if (idx != -1) {
						assertTrue(a[-(idx+2)] < x);
					}
				}
			}
		}
	}
	
	@Test
	public void testQsort() {
		int[][] x = new int[][]{
				{1},
				{1,1},
				{1,1,1},
				{2,1,1},
				{1,2,2},
				{1,2,3},
				{3,1,2},
				{3,2,1},
				{1,2,3,5,4}				
		};
		
		for (int i=0; i<x.length; i++) {
			int[] et = x[i].clone();
			int[] y = x[i].clone();
			Arrays.sort(et);
			Sorts.quickSort(x[i]);
			Sorts.heapSort(y);
			assertArrayEquals(et, x[i]);
			assertArrayEquals(et, y);
		}
				
	}
	
	@Test
	public void testBsearch2() {
		Assert.assertSame(0, Sorts.bsearch(new int[] {0}, 0));
		Assert.assertSame(-1, Sorts.bsearch(new int[] {0}, -1));
		Assert.assertSame(-2, Sorts.bsearch(new int[] {0}, 1));
		
		Assert.assertSame(0, Sorts.bsearch(new int[] {0, 0}, 0));
		Assert.assertSame(-1, Sorts.bsearch(new int[] {0, 0}, -1));
		Assert.assertSame(-3, Sorts.bsearch(new int[] {0, 0}, 1));
		
		Assert.assertSame(0, Sorts.bsearch(new int[] {0, 1, 1}, 0));
		Assert.assertSame(-1, Sorts.bsearch(new int[] {0, 1, 1}, -1));
		Assert.assertSame(1, Sorts.bsearch(new int[] {0, 1, 1}, 1));

	}
}
